package com.cskaoyan.javase.recursion._1basic;

import javax.xml.transform.sax.SAXTransformerFactory;

/**
 * 引例：
 * 使用递归计算N（N>=1）的阶乘（factorial）
 * n! =  n * (n-1) * (n-2)*...*1
 * 这个问题完全可以用循环来完成,循环求解重要的是找到被循环执行的语句
 *
 * 递归求解,肯定需要找到递归的两要素:
 *      1.递归体
 *      2.递归的出口
 *
 * 将大问题分解为小问题的思想就是递归的思想：
 *      1.把一个复杂的大规模的问题，分解成若干相似的小规模的子问题。
 *      2.当子问题规模足够小的时候，就可以直接得到小规模问题的解。
 *      3.然后把所有的小规模的子问题的解，组合起来，得到要求解的大规模问题的解。
 *
 * 如何来分解n!,把它简化呢?
 * n! =  n * (n-1)!
 * (n-1)! = (n-1) * (n-2)!
 * ...
 * 2! = 2 * 1!
 * 1! = 1
 * 那么以上分解过程,我们可以设对于n的阶乘,它的结果是f(n)
 * 那么:
 *      f(n) = n * f(n-1)    递归体语句
 *      而且: f(1) = 1       递归的出口
 *
 *
 * 不难发现递归的优点是：
 * 递归的代码会非常简洁，这是最直观的。
 * 人在解决问题的时候，都会下意识的分解问题。递归的思想很符合人的思维，用递归求解一个问题的思路很容易被人理解。
 * 接第二条，一旦能够找打分解问题的思路，递归会非常好用。
 *
 *
 * 当然递归的缺点也非常明显：
 *      1.不用递归时，往往一个方法就能解决问题。
 *      而递归会调用多个方法，占用大量栈内存，且明显存在重复计算，效率低。
 *      也就是说，使用递归求解一个问题，时间和空间复杂度都不占优势，既占用空间效率还低。
 *      实际上,递归是在计算机出现以后,利用了计算机的庞大算力,来暴力求解问题的一种方式.
 *      2.栈溢出错误警告！递归很危险，一旦栈溢出是严重错误！
 *
 综上，递归是一把伤人亦伤己的利器，实际开发中不要随意使用递归，使用递归要深思熟虑递归的深度和出口，避免栈溢出错误
 *
 * @since 14:48
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(factorialLoopSolution(10));
        System.out.println(factorialRecursionSolution(10));
    }

    public static long factorialRecursionSolution(int n) {
        // 写递归,先写递归的出口
        if (n == 1) {
            return 1;
        }
        return n * factorialRecursionSolution(n - 1);
    }

    public static long factorialLoopSolution(int n) {
        // n的阶乘就是从1一直乘到n
        int product = 1;
        for (int i = 1; i <= n; i++) {
            product *= i;
        }
        return product;
    }
}
